﻿#include <iostream>

static int recur(const char* text, size_t textSize, int index)
{
    if (index >= textSize)
    {
        return 1;
    }

    auto cur = text[index];
    if (cur == '0')
    {
        return 0;
    }

    int total = 0;
    switch (cur)
    {
    case '1':
        // 和后一个数字组合变字母，或者自己变字母
        {
            total += recur(text, textSize, index + 1);
            total += recur(text, textSize, index + 2);
        }
        break;

    case '2':
        {
            // 后一个数字是0-6, 才有可能组合变字母
            if (index + 1 < textSize)
            {
                auto next = text[index + 1];
                if ('0' <= next && next <= '6')
                {
                    total += recur(text, textSize, index + 2);
                }
            }

            total += recur(text, textSize, index + 1);
        }
        break;

    default:
        total += recur(text, textSize, index + 1);
        break;
    }

    return total;
}

static int byStrictTable(const char* text)
{
    auto textSize = strlen(text);
    int* dp = (int*)malloc((textSize + 1) * sizeof(int));
    memset(dp, 0, (textSize + 1) * sizeof(int));
    dp[textSize] = 1;

    for (int index = textSize - 1; index >= 0; --index)
    {
        auto cur = text[index];
        if (cur == '0') continue;

        int total = 0;
        switch (cur)
        {
        case '1':
            // 和后一个数字组合变字母，或者自己变字母
            {
                total += dp[index + 1];
                total += (index + 2 <= textSize) ? dp[index + 2] : 0;
            }
            break;

        case '2':
            {
                // 后一个数字是0-6, 才有可能组合变字母
                if (index + 1 < textSize)
                {
                    auto next = text[index + 1];
                    if ('0' <= next && next <= '6')
                    {
                        total += (index + 2 <= textSize) ? dp[index + 2] : 0;
                    }
                }

                total += dp[index + 1];
            }
            break;

        default:
            total += dp[index + 1];
            break;
        }

        dp[index] = total;
    }

    int res = dp[0];
    free(dp);
    return res;
}

// 将给定的数字转换为字符串，原则如下: 1对应'a', 2对应'b', ... 26对应'z', 例如12258，
// 可以转换为"abbeh", "aveh", "abyh", "lbeh"或者"lyh", 共5种可能性。
// 编写一个函数，给出可以转换的不同字符串有多少种.
int main_ConvertNumbersToCharacters()
{
    char text[256] = "12258";
    int count = recur(text, strlen(text), 0);
    printf("%d\n", count);
    count = byStrictTable(text);
    printf("%d\n", count);
    return 0;
}